package com.itheima.leetcode.od.b.bf;

import java.util.HashMap;

/**
 * <h3>套皮Leetcode76-最小覆盖子串</h3>
 * (A卷,100分)- 完美走位（Java & JS & Python）
 * <p>
 * 题目描述
 * <p>
 * 在第一人称射击游戏中，玩家通过键盘的A、S、D、W四个按键控制游戏人物分别向左、向后、向右、向前进行移动，从而完成走位。
 * <p>
 * 假设玩家每按动一次键盘，游戏任务会向某个方向移动一步，如果玩家在操作一定次数的键盘并且各个方向的步数相同时，此时游戏任务必定会回到原点，则称此次走位为完美走位。
 * <p>
 * 现给定玩家的走位（例如：ASDA），请通过更换其中一段连续走位的方式使得原走位能够变成一个完美走位。其中待更换的连续走位可以是相同长度的任何走位。
 * <p>
 * 请返回待更换的连续走位的最小可能长度。
 * <p>
 * 如果原走位本身是一个完美走位，则返回0。
 * <p>
 * 输入描述
 * <p>
 * 输入为由键盘字母表示的走位s，例如：ASDA
 * <p>
 * 输出描述
 * <p>
 * 输出为待更换的连续走位的最小可能长度。
 * <p>
 * 用例
 * <p>
 * 输入	WASDAASD
 * 输出	1
 * 说明	将第二个A替换为W，即可得到完美走位
 * 输入	AAAA
 * 输出	3
 * 说明	将其中三个连续的A替换为WSD，即可得到完美走位
 */
public class PerfectPositioning {
    public static void main(String[] args) {
        /*Scanner sc = new Scanner(System.in);
        System.out.println(getResult(sc.next()));*/

        System.out.println(getResult("WASDAASD"));
    }

    public static int getResult(String str) {

        // count用于记录W,A,S,D字母的数量
        HashMap<Character, Integer> count = new HashMap<>();
        for (int i = 0; i < str.length(); i++) {
            Character c = str.charAt(i);
            count.put(c, count.getOrDefault(c, 0) + 1);
        }

        // 平衡状态时，W,A,S,D应该都是avg数量
        int avg = str.length() / 4;
        // total用于记录多余字母个数
        int total = 0;
        // flag表示当前是否为平衡状态，默认是
        boolean flag = true;
        int[] targetCount = new int[128]; // 阿斯克码一共有128个字符编码。‌
        for (Character c : count.keySet()) {
            if (count.get(c) > avg) {
                // 如果有一个字母数量超标，则平衡打破
                flag = false;
                // 此时count记录每个字母超过avg的数量
                targetCount[c] = count.get(c) - avg;
                total += targetCount[c];
            }
        }

        // 如果平衡，则输出0
        if (flag) {
            return 0;
        }

        int passed = 0; // 已通过的条件数
        int i = 0; // 左边界
        int j = 0; // 右边界
        int minLen = str.length() + 1;
        char[] source = str.toCharArray();
        int[] sourceCount = new int[128]; // 原始串 i~j 范围内字符各出现次数
        while (j < source.length) {
            // 扩大 j 范围，更新范围内字符计数 和 通过条件数
            char right = source[j];
            sourceCount[right]++;
            if (sourceCount[right] == targetCount[right]) { // 如果超过 targetCount[right] 仍会累加，相同字母 passed 只累加一次
                passed++;
            }
            // 若已满足所有条件，缩小 i 范围，更新范围内字符计数 和 通过条件数
            while (total == passed && i <= j) {
                minLen = Math.min(minLen, j - i + 1);
                char left = source[i];
                sourceCount[left]--;
                if (sourceCount[left] < targetCount[left]) {
                    passed--;
                }
                i++;
            }
            j++;
        }
        return minLen;
    }
}